/*
 * map.cpp
 *
 * Copyright (C) 1999, Ben Swartzlander
 * This file is part of Q2BotCore.
 * For conditions of distribution and use,
 * see the accompanying README file.
 */

#include <fcntl.h>
#include <io.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include "util.h"
#include "quakebot.h"

#define VERSION_STRING "q2map.dll - v0.41 BUILD 51 (27/7/09)\n"

// File info

char *quake2Directory=NULL;
char *gameDirectory=NULL;

// Map info

bool loaded=false;

plane_t *planes=NULL;
vertex_t *vertexes=NULL;
node_t *nodes=NULL;
face_t *faces=NULL;
unsigned short *leaffaces=NULL;
leaf_t *leafs=NULL;
int *surfedges=NULL;
edge_t *edges=NULL;
model_t *models=NULL;

int planeCount;
int vertexCount;
int nodeCount;
int faceCount;
int leaffaceCount;
int leafCount;
int edgeCount;
int surfedgeCount;
int modelCount;

// Extended map info

xface_t *xfaces=NULL;
link_t *links=NULL;
edgeface_t *edgefaces=NULL;
int *edgefriends=NULL;
xedge_t *xedges=NULL;
int *sortededges=NULL;

unsigned short linkCount;
int edgefriendCount;

// A cache for data in the search function

int *dist=NULL;
int s_lists[256][256];
int s_listnum[256];
int path[256];

// Inline profiling

__int64	i64_clock_start,i64_clock_end,i64_search_time,i64_max_search_time;
double cpuFreq=100000000.0;

// Utility

int whichLeaf(vec3_t p);
int whichFace(vec3_t p);

// Exported Functions

void qmMarkLinkInvalid(int link) {
	if(link<0 || link>65535) {
		return;
	}
	links[link].valid=false;
}

void qxArraySizes(int *edgelineCount, int *linklineCount) {
	int i,m;
	int count;

	count=0;
	for(m=0;m<modelCount;m++) {
		for(i=0;i<models[m].numfaces;i++) {
			count+=xfaces[i].numlinks;
		}
	}

	*edgelineCount=edgeCount;
	*linklineCount=count*2;
}

bool qxFillArrays(vec3_t **edgelines, vec3_t **linklines) {
	int i,j;
	int firstlink,lastlink;
	int face;
	int m;
	int edgelineCount,linklineCount;

	edgelineCount=edgeCount;

	for(i=0;i<edgelineCount;i++) {
		(*edgelines)[2*i][0]=vertexes[edges[i].v[0]].origin[0];
		(*edgelines)[2*i][1]=vertexes[edges[i].v[0]].origin[1];
		(*edgelines)[2*i][2]=vertexes[edges[i].v[0]].origin[2];

		(*edgelines)[2*i+1][0]=vertexes[edges[i].v[1]].origin[0];
		(*edgelines)[2*i+1][1]=vertexes[edges[i].v[1]].origin[1];
		(*edgelines)[2*i+1][2]=vertexes[edges[i].v[1]].origin[2];
	}

	linklineCount=0;
	for(m=0;m<modelCount;m++) {
		for(i=0;i<models[m].numfaces;i++) {
			linklineCount+=xfaces[i].numlinks;
		}
	}
	linklineCount*=2;

	linklineCount=0;
	for(m=0;m<modelCount;m++) {
		for(i=0;i<models[m].numfaces;i++) {
			firstlink=xfaces[i].firstlink;
			lastlink=firstlink+xfaces[i].numlinks;
			for(j=firstlink;j<lastlink;j++) {
				face=links[j].face;

				(*linklines)[2*linklineCount][0]=xfaces[i].origin[0];
				(*linklines)[2*linklineCount][1]=xfaces[i].origin[1];
				(*linklines)[2*linklineCount][2]=xfaces[i].origin[2];

				(*linklines)[2*linklineCount+1][0]=links[j].origin[0];
				(*linklines)[2*linklineCount+1][1]=links[j].origin[1];
				(*linklines)[2*linklineCount+1][2]=links[j].origin[2];

				linklineCount++;

				(*linklines)[2*linklineCount][0]=xfaces[face].origin[0];
				(*linklines)[2*linklineCount][1]=xfaces[face].origin[1];
				(*linklines)[2*linklineCount][2]=xfaces[face].origin[2];

				(*linklines)[2*linklineCount+1][0]=links[j].origin[0];
				(*linklines)[2*linklineCount+1][1]=links[j].origin[1];
				(*linklines)[2*linklineCount+1][2]=links[j].origin[2];
				
				linklineCount++;
			}
		}
	}
	return true;
}

void wanderPath(vec3_t o,path_t *vpath) {
	int face,link,face2;
	int i,j,k;
	int numlinks;
	int list[256];
	int list2[256];

	vpath->length=0;

	if(whichLeaf(o)==0) {
		print("Player is not in map\n");
		return;
	}
	face=whichFace(o);
	if(face==-1) {
		return;
	}
	for(i=0;i<faceCount;i++) {
		dist[i]=-1;
	}
	if(face>=faceCount || face<0) {
		printe("Internal error: Array Out of Bounds: dist[%d/%d]\n",face,faceCount);
		return;
	}
	dist[face]=0;

	vpath->points[0][0]=xfaces[face].origin[0];
	vpath->points[0][1]=xfaces[face].origin[1];
	vpath->points[0][2]=xfaces[face].origin[2]+24.0;
	vpath->length=1;

	for(i=0;i<256;i++) {
		if(face>=faceCount || face<0) {
			printe("Internal error: Array Out of Bounds: xfaces[%d/%d]\n",face,faceCount);
			return;
		}
		numlinks=xfaces[face].numlinks;
		if(numlinks>256) {
			numlinks=256;
		}
		for(j=0;j<numlinks;j++) {
			list2[j]=xfaces[face].firstlink+j;
		}
		for(j=numlinks-1;j>=0;j--) {
			k=irand()%(j+1);
			list[j]=list2[k];
			list2[k]=list2[j-1];
		}
		for(j=0;j<numlinks;j++) {
			link=list[j];
			if(link>=linkCount || link<0) {
				printe("Internal error: Array Out of Bounds: links[%d/%d]\n",link,linkCount);
				return;
			}
			if(!links[link].valid) {
				continue;
			}
			face2=links[link].face;
			if(face2>=faceCount || face2<0) {
				printe("Internal error: Array Out of Bounds: dist[%d/%d]\n",face2,faceCount);
				return;
			}
			if(dist[face2]==-1) {
				dist[face2]=0;
				face=face2;
				vpath->points[2*i+1][0]=links[link].origin[0];
				vpath->points[2*i+1][1]=links[link].origin[1];
				vpath->points[2*i+1][2]=links[link].origin[2]+24.0;
				vpath->points[2*i+2][0]=xfaces[face].origin[0];
				vpath->points[2*i+2][1]=xfaces[face].origin[1];
				vpath->points[2*i+2][2]=xfaces[face].origin[2]+24.0;
				vpath->links[i]=link;
				vpath->length=2*i+3;
				break;
			}
		}
		if(j==numlinks) {
			return;
		}
	}
}

bool findPath(vec3_t o,vec3_t p,path_t *vpath,bool full) {
	int startface,endface,face,link,index,face2;
	bool found=false;
	int s_far;
	int i,j,k;

	s_far=0;
	if(whichLeaf(o)==0) {
		print("Player is not in map\n");
		return false;
	}
	if(whichLeaf(p)==0) {
		print("Target is not in map\n");
		return false;
	}
	startface=whichFace(o);
	endface=whichFace(p);
	if(startface==-1 || endface==-1) {
		return false;
	}
	for(i=0;i<faceCount;i++) {
		dist[i]=-1;
	}
	s_lists[0][0]=startface;
	s_listnum[0]=1;
	if(startface>=faceCount || startface<0) {
		printe("Internal error: Array Out of Bounds: dist[%d/%d]\n",startface,faceCount);
		return false;
	}
	dist[startface]=0;
	while(!found) {
		s_far++;
		if(s_far>=250) {
			return false;
		}
		s_listnum[s_far]=0;
		for(i=0;i<s_listnum[s_far-1];i++) {
			face=s_lists[s_far-1][i];
			if(face>=faceCount || face<0) {
				printe("Internal error: Array Out of Bounds: xfaces[%d/%d]\n",face,faceCount);
				return false;
			}
			for(j=0;j<xfaces[face].numlinks;j++) {
				link=xfaces[face].firstlink+j;
				if(link>=linkCount || link<0) {
				printe("Internal error: Array Out of Bounds: links[%d/%d]\n",link,linkCount);
					return false;
				}
				if(!links[link].valid) {
					continue;
				}
				face2=links[link].face;
				if(face2>=faceCount || face2<0) {
				printe("Internal error: Array Out of Bounds: dist[%d/%d]\n",face2,faceCount);
					return false;
				}
				if(face2==endface) {
					found=true;
				}
				if(dist[face2]==-1) {
					dist[face2]=s_far;
					index=s_listnum[s_far];
					if(index>=256) {
						printe("Too many faces at distance: %d\n",s_far);
						return false;
					}
					s_lists[s_far][index]=face2;
					s_listnum[s_far]++;
				}
			}
		}
	}
	vpath->length=s_far*2+1;
	if(!full) {
		return true;
	}
	face2=endface;
	for(i=s_far-1;i>=0;i--) {
		found=false;
		for(j=0;!found;j++) {
			face=s_lists[i][j];
			for(k=0;k<xfaces[face].numlinks;k++) {
				link=xfaces[face].firstlink+k;
				if(links[link].face==face2) {
					found=true;
					path[i]=link;
				}
			}
		}
		face2=face;
	}
	vpath->points[0][0]=xfaces[startface].origin[0];
	vpath->points[0][1]=xfaces[startface].origin[1];
	vpath->points[0][2]=xfaces[startface].origin[2]+24.0;
	for(i=0;i<s_far;i++) {
		vpath->points[2*i+1][0]=links[path[i]].origin[0];
		vpath->points[2*i+1][1]=links[path[i]].origin[1];
		vpath->points[2*i+1][2]=links[path[i]].origin[2]+24.0;
		vpath->points[2*i+2][0]=xfaces[links[path[i]].face].origin[0];
		vpath->points[2*i+2][1]=xfaces[links[path[i]].face].origin[1];
		vpath->points[2*i+2][2]=xfaces[links[path[i]].face].origin[2]+24.0;
		vpath->links[i]=path[i];
	}
	return true;
}

bool qmFindPath(vec3_t o,vec3_t p,path_t *vpath,bool full) {
	bool found;
	__int64	i64_start,i64_end;

	if(!loaded) return false;
	if(!vpath) return false;

	if(*((int *)&(vpath->points[0][0]))==-1) {
		wanderPath(o,vpath);
		return true;
	}

	RDTSC(i64_start);

	found=findPath(o,p,vpath,full);

	RDTSC(i64_end);

	i64_search_time+=(i64_end-i64_start);
	if((i64_end-i64_start)>i64_max_search_time) {
		i64_max_search_time=(i64_end-i64_start);
	}

	return found;
}

int whichLeaf(vec3_t p) {
	int nextnode=models[0].rootnode;
	plane_t *plane;

	while(nextnode>=0) {
		plane=&(planes[nodes[nextnode].planenum]);
		if(plane->type==0) {
			if((p[0]*plane->normal[0])<plane->dist) {
				nextnode=nodes[nextnode].back;
			} else {
				nextnode=nodes[nextnode].front;
			}
		} else if(plane->type==1) {
			if((p[1]*plane->normal[1])<plane->dist) {
				nextnode=nodes[nextnode].back;
			} else {
				nextnode=nodes[nextnode].front;
			}
		} else if(plane->type==2) {
			if((p[2]*plane->normal[2])<plane->dist) {
				nextnode=nodes[nextnode].back;
			} else {
				nextnode=nodes[nextnode].front;
			}
		} else {
			if((p[0]*plane->normal[0]+p[1]*plane->normal[1]+p[2]*plane->normal[2])<plane->dist) {
				nextnode=nodes[nextnode].back;
			} else {
				nextnode=nodes[nextnode].front;
			}
		}
	}
	return (-1-nextnode);
}

int whichFace(vec3_t p) {
	int leaf;
	int firstface,lastface,face;
	int firstedge,lastedge,edge;
	int v0,v1;
	int hits,possible;
	float dx,dy,t;
	int i,j;

	leaf=whichLeaf(p);
	firstface=leafs[leaf].firstleafface;
	lastface=leafs[leaf].numleaffaces+firstface;
	possible=0;

	for(i=firstface;i<lastface;i++) {
		face=leaffaces[i];
		if(xfaces[face].type&0x00000001) {
			firstedge=faces[face].firstedge;
			lastedge=faces[face].numedges+firstedge;
			hits=0;
			for(j=firstedge;j<lastedge;j++) {
				edge=surfedges[j];
				if(edge>0) {
					v0=edges[edge].v[0];
					v1=edges[edge].v[1];
				} else {
					edge=-edge;
					v0=edges[edge].v[1];
					v1=edges[edge].v[0];
				}
				dx=vertexes[v1].origin[0]-vertexes[v0].origin[0];
				dy=vertexes[v1].origin[1]-vertexes[v0].origin[1];
				if(dy==0) {
					if(p[1]==vertexes[v0].origin[1]) {
						if(p[0]>=vertexes[v0].origin[0] && p[0]<=vertexes[v1].origin[0]) {
							return face;
						}
						if(p[0]>=vertexes[v1].origin[0] && p[0]<=vertexes[v0].origin[0]) {
							return face;
						}
					}
				} else {
					t=(p[1]-vertexes[v0].origin[1])/dy;
					if((t<1)&&(t>=0)) {
						if((t*dx+vertexes[v0].origin[0])==p[0]) {
							return face;
						} else if((t*dx+vertexes[v0].origin[0])>=p[0]) {
							hits++;
						}
					}
				}
			}
			if(hits==1) {
				return face;
			}
		}
	}
	return -1;
}

int qmGetBSPLeaf(vec3_t p) {

	if(!loaded) return 0;

	return whichLeaf(p);
}

int qmLeafContents(int leaf) {

	if(!loaded) return 0;

	if(leaf>=leafCount) return -1;

	return leafs[leaf].contents;
}

// Traceline

bool intersectBSPLeaf(int leaf, int mask) {

	if(leaf==0) {
		printe("Error in qmTraceLine(): leaf=0\n");
		return true;
	}

	if(leafs[leaf].contents&mask) {
		return true;
	} else {
		return false;
	}
}

float intersectBSPTree(vec3_t o, vec3_t p, int node, float min, float max, int mask) {
	float tx,ty,tz;
	float nx,ny,nz;
	float pdist,t;
	float temp;
	int near_node,far_node;
	int plane_id;
	float test;

	plane_id=nodes[node].planenum;
	tx=p[0]-o[0];
	ty=p[1]-o[1];
	tz=p[2]-o[2];
	nx=planes[plane_id].normal[0];
	ny=planes[plane_id].normal[1];
	nz=planes[plane_id].normal[2];
	pdist=planes[plane_id].dist;
	if(planes[plane_id].type==0) {
		if(tx!=0) {
			t=(nx*pdist-o[0])/tx;
		} else {
			t=999999;
		}
		if((o[0]*nx)<pdist) {
			near_node=nodes[node].back;
			far_node=nodes[node].front;
		} else {
			near_node=nodes[node].front;
			far_node=nodes[node].back;
		}
	} else if(planes[plane_id].type==1) {
		if(ty!=0) {
			t=(ny*pdist-o[1])/ty;
		} else {
			t=999999;
		}
		if((o[1]*ny)<pdist) {
			near_node=nodes[node].back;
			far_node=nodes[node].front;
		} else {
			near_node=nodes[node].front;
			far_node=nodes[node].back;
		}
	} else if(planes[plane_id].type==2) {
		if(tz!=0) {
			t=(nz*pdist-o[2])/tz;
		} else {
			t=999999;
		}
		if((o[2]*nz)<pdist) {
			near_node=nodes[node].back;
			far_node=nodes[node].front;
		} else {
			near_node=nodes[node].front;
			far_node=nodes[node].back;
		}
	} else {
		temp=nx*tx+ny*ty+nz*tz;
		if(temp!=0) {
			t=(pdist-o[0]*nx-o[1]*ny-o[2]*nz)/temp;
		} else {
			t=999999;
		}
		if((o[0]*nx+o[1]*ny+o[2]*nz)<pdist) {
			near_node=nodes[node].back;
			far_node=nodes[node].front;
		} else {
			near_node=nodes[node].front;
			far_node=nodes[node].back;
		}
	}
	if((t>=max)||(t<=0)) {
		if(near_node<0) {
			if(intersectBSPLeaf(-1-near_node,mask)) {
				return min;
			} else {
				return 1.0;
			}			
		} else {
			return intersectBSPTree(o,p,near_node,min,max,mask);
		}
	} else if(t<=min) {
		if(far_node<0) {
			if(intersectBSPLeaf(-1-far_node,mask)) {
				return min;
			} else {
				return 1.0;
			}
		} else {
			return intersectBSPTree(o,p,far_node,min,max,mask);
		}
	} else {
		if(near_node<0) {
			if(intersectBSPLeaf(-1-near_node,mask)) {
				test=min;
			} else {
				test=1.0;
			}
		} else {
			test=intersectBSPTree(o,p,near_node,min,t,mask);
		}
		if(test<1.0) {
			return test;
		} else {
			if(far_node<0) {
				if(intersectBSPLeaf(-1-far_node,mask)) {
					return t;
				} else {
					return 1.0;
				}
			} else {
				return intersectBSPTree(o,p,far_node,t,max,mask);
			}
		}
	}
}

float traceLine(vec3_t o,vec3_t p) {
	return intersectBSPTree(o,p,models[0].rootnode,0.0,1.0,0x00000003);
}

float qmTraceLine(vec3_t o,vec3_t p,int mask) {

	if(!loaded) return 0.0;
	if(!mask) return 1.0;

	return intersectBSPTree(o,p,models[0].rootnode,0.0,1.0,mask);
}

// BSP Functions

bool edgeOverlap(int n,int m) {
	bool p,q;
	float x1,x2,x3,x4,y1,y2,y3,y4,temp;

	x1=vertexes[edges[n].v[0]].origin[0];
	x2=vertexes[edges[n].v[1]].origin[0];
	x3=vertexes[edges[m].v[0]].origin[0];
	x4=vertexes[edges[m].v[1]].origin[0];
	y1=vertexes[edges[n].v[0]].origin[1];
	y2=vertexes[edges[n].v[1]].origin[1];
	y3=vertexes[edges[m].v[0]].origin[1];
	y4=vertexes[edges[m].v[1]].origin[1];

	if(x1>x2) { temp=x1; x1=x2; x2=temp; }
	if(x3>x4) { temp=x3; x3=x4; x4=temp; }
	if(y1>y2) { temp=y1; y1=y2; y2=temp; }
	if(y3>y4) { temp=y3; y3=y4; y4=temp; }

	p=((x1<=x3 && x3<x2) || (x3<=x1 && x1<x4) || (x1==x2 && (x1==x3 || x1==x4)) || (x3==x4 && (x3==x1 || x3==x2)));
	q=((y1<=y3 && y3<y2) || (y3<=y1 && y1<y4) || (y1==y2 && (y1==y3 || y1==y4)) || (y3==y4 && (y3==y1 || y3==y2)));

	return (p&&q);
}

float heightBetween(int n,int m) {
	float z1,z2,z3,z4;

	z1=vertexes[edges[n].v[0]].origin[2];
	z2=vertexes[edges[n].v[1]].origin[2];
	z3=vertexes[edges[m].v[0]].origin[2];
	z4=vertexes[edges[m].v[1]].origin[2];
	return ((z3+z4-z1-z2)/2);
}

bool checkWall(int wall,int face,int edge) {
	int j,k,l,n;
//	int i,m;
	float height;

	for(j=0;j<faces[wall].numedges;j++) {
		k=surfedges[j+faces[wall].firstedge];
		if(k<0) {
			k=-k;
		}
		height=heightBetween(edge,k);
		if(edgeOverlap(edge,k) && height<=24.0) {
			if(edgefaces[k].face[0]==wall) {
				if(xfaces[edgefaces[k].face[1]].type&0x00000001 && edgefaces[k].face[1]!=face) {
// change k to edge
					links[linkCount].face=(unsigned short)edgefaces[k].face[1];
					links[linkCount].origin[0]=(vertexes[edges[edge].v[0]].origin[0]+vertexes[edges[edge].v[1]].origin[0])/2;
					links[linkCount].origin[1]=(vertexes[edges[edge].v[0]].origin[1]+vertexes[edges[edge].v[1]].origin[1])/2;
					links[linkCount].origin[2]=(vertexes[edges[edge].v[0]].origin[2]+vertexes[edges[edge].v[1]].origin[2])/2;
					links[linkCount].valid=true;
					xfaces[face].numlinks++;
					linkCount++;
				}
			} else if(edgefaces[k].face[1]==wall) {
				if(xfaces[edgefaces[k].face[0]].type&0x00000001 && edgefaces[k].face[0]!=face) {
// change k to edge
					links[linkCount].face=(unsigned short)edgefaces[k].face[0];
					links[linkCount].origin[0]=(vertexes[edges[edge].v[0]].origin[0]+vertexes[edges[edge].v[1]].origin[0])/2;
					links[linkCount].origin[1]=(vertexes[edges[edge].v[0]].origin[1]+vertexes[edges[edge].v[1]].origin[1])/2;
					links[linkCount].origin[2]=(vertexes[edges[edge].v[0]].origin[2]+vertexes[edges[edge].v[1]].origin[2])/2;
					links[linkCount].valid=true;
					xfaces[face].numlinks++;
					linkCount++;
				}
			} else {
				printe("Critical Error: Neither face links back to original\n");
				return false;
			}
			if(linkCount==65535) {
				printe("Critical Error: Maximum links exceeded\n");
				return false;
			}
		}

		for(l=0;l<xedges[k].numfriends;l++) {
			n=edgefriends[xedges[k].firstfriend+l];

			height=heightBetween(edge,n);
// change k to n
			if(edgeOverlap(edge,n) && height<=24.0) {
				if(edgefaces[n].face[0]!=-1) {
					if(xfaces[edgefaces[n].face[0]].type&0x00000001) {
// change n to edge
						links[linkCount].face=(unsigned short)edgefaces[n].face[0];
						links[linkCount].origin[0]=(vertexes[edges[edge].v[0]].origin[0]+vertexes[edges[edge].v[1]].origin[0])/2;
						links[linkCount].origin[1]=(vertexes[edges[edge].v[0]].origin[1]+vertexes[edges[edge].v[1]].origin[1])/2;
						links[linkCount].origin[2]=(vertexes[edges[edge].v[0]].origin[2]+vertexes[edges[edge].v[1]].origin[2])/2;
						links[linkCount].valid=true;
						xfaces[face].numlinks++;
						linkCount++;
					}
				} else if(edgefaces[n].face[1]!=-1) {
// change n to edge
					if(xfaces[edgefaces[n].face[1]].type&0x00000001) {
						links[linkCount].face=(unsigned short)edgefaces[n].face[1];
						links[linkCount].origin[0]=(vertexes[edges[edge].v[0]].origin[0]+vertexes[edges[edge].v[1]].origin[0])/2;
						links[linkCount].origin[1]=(vertexes[edges[edge].v[0]].origin[1]+vertexes[edges[edge].v[1]].origin[1])/2;
						links[linkCount].origin[2]=(vertexes[edges[edge].v[0]].origin[2]+vertexes[edges[edge].v[1]].origin[2])/2;
						links[linkCount].valid=true;
						xfaces[face].numlinks++;
						linkCount++;
					}
				}
				if(linkCount==65535) {
					printe("Critical Error: Maximum links exceeded\n");
					return false;
				}
			}
		}
	}
	return true;
}

int partition1(int p,int r) {
	int i,j;
	unsigned short pivot;
	int temp;

	pivot=xedges[sortededges[p]].key;
	i=p-1;
	j=r;
	while(1) {
		do {
			j--;
		} while(pivot<xedges[sortededges[j]].key);
		do {
			i++;
		} while(pivot>xedges[sortededges[i]].key);
		if(i<j) {
			temp=sortededges[j];
			sortededges[j]=sortededges[i];
			sortededges[i]=temp;
		} else {
			return j+1;
		}
	}
}

void quicksort1(int p,int r) {
	int q;

	if((r-p)>1) {
		q=partition1(p,r);
		quicksort1(p,q);
		quicksort1(q,r);
	}
}

int partition2(int p,int r) {
	int i,j;
	unsigned int pivot;
	int temp;

	pivot=xedges[sortededges[p]].key2;
	i=p-1;
	j=r;
	while(1) {
		do {
			j--;
		} while(pivot<xedges[sortededges[j]].key2);
		do {
			i++;
		} while(pivot>xedges[sortededges[i]].key2);
		if(i<j) {
			temp=sortededges[j];
			sortededges[j]=sortededges[i];
			sortededges[i]=temp;
		} else {
			return j+1;
		}
	}
}

void quicksort2(int p,int r) {
	int q;

	if((r-p)>1) {
		q=partition2(p,r);
		quicksort2(p,q);
		quicksort2(q,r);
	}
}

bool colinear(int m,int n) {
	vec3_t u;
	unsigned char yaw,pitch;
	unsigned short key;
	
	u[0]=vertexes[edges[n].v[0]].origin[0]-vertexes[edges[m].v[0]].origin[0];
	u[1]=vertexes[edges[n].v[0]].origin[1]-vertexes[edges[m].v[0]].origin[1];
	u[2]=vertexes[edges[n].v[0]].origin[2]-vertexes[edges[m].v[0]].origin[2];
	pitch=(unsigned char)(pitchFromVect(u)*256.0/PI);
	yaw=(unsigned char)(yawFromVect(u)*256.0/PI);
	key=yaw+(pitch<<8);
	return (key==xedges[m].key && key==xedges[n].key);
}

bool findFriends2(int start,int end) {
	int i,j;
	unsigned int key2=0;
	int first,last;
	int edge,edge2;

	for(i=start;i<end;i++) {
		edge=sortededges[i];
		xedges[edge].firstfriend=edgefriendCount;
		xedges[edge].numfriends=0;

		if(xedges[edge].key2!=key2) {
			key2=xedges[edge].key2;
			for(first=start;xedges[sortededges[first]].key2!=key2;first++) {
				;
			}
			for(last=first;xedges[sortededges[last]].key2==key2;last++) {
				if(last==end-1) {
					break;
				}
			}
		}
		for(j=first;j<last;j++) {
			edge2=sortededges[j];
			if(edge2!=edge) {
				if(edgeOverlap(edge,edge2)) {
					if(colinear(edge,edge2)) {
						edgefriends[edgefriendCount]=edge2;
						xedges[edge].numfriends++;
						edgefriendCount++;
					}
				}
			}
			if(edgefriendCount==65535) {
				printe("Critical Error: Edge friend table overflow\n");
				return false;
			}
		}
	}
	return true;
}

bool findFriends(void) {
	int i,j;
	unsigned short key=65535;
	bool flag=true;
	int first,last;
	int edge,edge2;

	edgefriendCount=0;

	for(i=0;i<edgeCount;i++) {
		flag=true;
		edge=sortededges[i];
		xedges[edge].firstfriend=edgefriendCount;
		xedges[edge].numfriends=0;
		if(xedges[edge].key!=key) {
			key=xedges[edge].key;
			for(first=0;xedges[sortededges[first]].key!=key;first++) {
				;
			}
			for(last=first;xedges[sortededges[last]].key==key;last++) {
				if(last==edgeCount-1) {
					break;
				}
			}
//			fprintf(stream,"Key: %d First: %d Last %d\n",key,first,last);
			if(key==0 || key==128 || key==32896) {
				flag=false;
				quicksort2(first,last);
				if(!findFriends2(first,last)) {
					return false;
				}
				i=last-1;
			}
		}
		if(flag) {
			for(j=first;j<last;j++) {
				edge2=sortededges[j];
				if(edge2!=edge) {
					if(edgeOverlap(edge,edge2)) {
						if(colinear(edge,edge2)) {
							edgefriends[edgefriendCount]=edge2;
							xedges[edge].numfriends++;
							edgefriendCount++;
						}
					}
				}
				if(edgefriendCount==65535) {
					printe("Critical Error: Edge friend table overflow\n");
					return false;
				}
			}
		}
	}
	return true;
}

bool linkMap(void) {
	int i,j,k,l,m,n;
	float f;
	vec3_t u;
	int v;

	links=(link_t *)malloc(65536*sizeof(link_t));
	edgefriends=(int *)malloc(65536*sizeof(int));

	edgefaces=(edgeface_t *)malloc(edgeCount*sizeof(edgeface_t));
	xedges=(xedge_t *)malloc(edgeCount*sizeof(xedge_t));
	sortededges=(int *)malloc(edgeCount*sizeof(int));
	for(i=0;i<edgeCount;i++) {
		edgefaces[i].face[0]=-1;
		edgefaces[i].face[1]=-1;
		u[0]=vertexes[edges[i].v[1]].origin[0]-vertexes[edges[i].v[0]].origin[0];
		u[1]=vertexes[edges[i].v[1]].origin[1]-vertexes[edges[i].v[0]].origin[1];
		u[2]=vertexes[edges[i].v[1]].origin[2]-vertexes[edges[i].v[0]].origin[2];
		xedges[i].pitch=(unsigned char)(pitchFromVect(u)*256.0/PI);
		xedges[i].yaw=(unsigned char)(yawFromVect(u)*256.0/PI);
		xedges[i].key=(unsigned short)xedges[i].yaw+(((unsigned short)xedges[i].pitch)<<8);
		switch(xedges[i].key) {
			case 0:
				xedges[i].key2=((unsigned int)(vertexes[edges[i].v[0]].origin[1]+32768.0))&0xffff+(((unsigned int)(vertexes[edges[i].v[0]].origin[2]+32768.0))<<16);
				break;

			case 128:
				xedges[i].key2=((unsigned int)(vertexes[edges[i].v[0]].origin[0]+32768.0))&0xffff+(((unsigned int)(vertexes[edges[i].v[0]].origin[2]+32768.0))<<16);
				break;

			case 32896:
				xedges[i].key2=((unsigned int)(vertexes[edges[i].v[0]].origin[0]+32768.0))&0xffff+(((unsigned int)(vertexes[edges[i].v[0]].origin[1]+32768.0))<<16);
				break;

			default:
				xedges[i].key2=0;
				break;
		}
		sortededges[i]=i;
	}
	quicksort1(0,edgeCount);

	if(!findFriends()) {
		return false;
	}
	xfaces=(xface_t *)malloc(faceCount*sizeof(xface_t));
	for(i=0;i<faceCount;i++) {
		xfaces[i].type=0;
		if(planes[faces[i].planenum].normal[2]>0.7 && faces[i].side==0) {
			xfaces[i].type|=0x00000001;
		} else {
			xfaces[i].type&=0xfffffffe;
		}
		if(planes[faces[i].planenum].normal[2]==0.0) {
			xfaces[i].type|=0x00000002;
		} else {
			xfaces[i].type&=0xfffffffd;
		}
		xfaces[i].origin[0]=0.0;
		xfaces[i].origin[1]=0.0;
		xfaces[i].origin[2]=0.0;
		f=1.0/(float)faces[i].numedges;
		for(j=0;j<faces[i].numedges;j++) {
			k=surfedges[j+faces[i].firstedge];
			if(k>0) {
				v=edges[k].v[0];
			} else {
				k=-k;
				v=edges[k].v[1];
			}
			xfaces[i].origin[0]+=vertexes[v].origin[0]*f;
			xfaces[i].origin[1]+=vertexes[v].origin[1]*f;
			xfaces[i].origin[2]+=vertexes[v].origin[2]*f;
			if(edgefaces[k].face[0]==-1) {
				edgefaces[k].face[0]=i;
			}  else if(edgefaces[k].face[1]==-1) {
				edgefaces[k].face[1]=i;
			} else {
				printe("Critical Error: More than 2 faces reference same edge\n");
				return false;
			}
		}
		xfaces[i].firstlink=0;
		xfaces[i].numlinks=0;
	}

	linkCount=0;

	for(m=0;m<modelCount;m++) {
		for(i=0;i<models[m].numfaces;i++) {
			xfaces[i].firstlink=linkCount;
			xfaces[i].numlinks=0;
			if(xfaces[i].type&0x00000001) {
				for(j=0;j<faces[i].numedges;j++) {
					k=surfedges[j+faces[i].firstedge];
					if(k<0) {
						k=-k;
					}
					if(edgefaces[k].face[0]==i) {
						if(edgefaces[k].face[1]!=-1) {
							if(xfaces[edgefaces[k].face[1]].type&0x00000001) {
								links[linkCount].face=(unsigned short)edgefaces[k].face[1];
								links[linkCount].origin[0]=(vertexes[edges[k].v[0]].origin[0]+vertexes[edges[k].v[1]].origin[0])/2;
								links[linkCount].origin[1]=(vertexes[edges[k].v[0]].origin[1]+vertexes[edges[k].v[1]].origin[1])/2;
								links[linkCount].origin[2]=(vertexes[edges[k].v[0]].origin[2]+vertexes[edges[k].v[1]].origin[2])/2;
								links[linkCount].valid=true;
								xfaces[i].numlinks++;
								linkCount++;
							} else if(xfaces[edgefaces[k].face[1]].type&0x00000002) {
								if(!checkWall(edgefaces[k].face[1],i,k)) {
									return false;
								}
							}
						}
					} else if(edgefaces[k].face[1]==i) {
						if(edgefaces[k].face[0]!=-1) {
							if(xfaces[edgefaces[k].face[0]].type&0x00000001) {
								links[linkCount].face=(unsigned short)edgefaces[k].face[0];
								links[linkCount].origin[0]=(vertexes[edges[k].v[0]].origin[0]+vertexes[edges[k].v[1]].origin[0])/2;
								links[linkCount].origin[1]=(vertexes[edges[k].v[0]].origin[1]+vertexes[edges[k].v[1]].origin[1])/2;
								links[linkCount].origin[2]=(vertexes[edges[k].v[0]].origin[2]+vertexes[edges[k].v[1]].origin[2])/2;
								links[linkCount].valid=true;
								xfaces[i].numlinks++;
								linkCount++;
							} else if(xfaces[edgefaces[k].face[0]].type&0x00000002) {
								if(!checkWall(edgefaces[k].face[0],i,k)) {
									return false;
								}
							}
						}
					} else {
						printe("Critical Error: Neither face links back to original\n");
						return false;
					}
					if(linkCount==65535) {
						printe("Critical Error: Maximum links exceeded\n");
						return false;
					}

					for(l=0;l<xedges[k].numfriends;l++) {
						n=edgefriends[xedges[k].firstfriend+l];

						if(edgefaces[n].face[0]!=-1) {
							if(xfaces[edgefaces[n].face[0]].type&0x00000001) {
// change n to k
								links[linkCount].face=(unsigned short)edgefaces[n].face[0];
								links[linkCount].origin[0]=(vertexes[edges[k].v[0]].origin[0]+vertexes[edges[k].v[1]].origin[0])/2;
								links[linkCount].origin[1]=(vertexes[edges[k].v[0]].origin[1]+vertexes[edges[k].v[1]].origin[1])/2;
								links[linkCount].origin[2]=(vertexes[edges[k].v[0]].origin[2]+vertexes[edges[k].v[1]].origin[2])/2;
								links[linkCount].valid=true;
								xfaces[i].numlinks++;
								linkCount++;
							} else if(xfaces[edgefaces[n].face[0]].type&0x00000002) {
								if(!checkWall(edgefaces[n].face[0],i,n)) {
									return false;
								}
							}
						} else if(edgefaces[n].face[1]!=-1) {
							if(xfaces[edgefaces[n].face[1]].type&0x00000001) {
// change n to k
								links[linkCount].face=(unsigned short)edgefaces[n].face[1];
								links[linkCount].origin[0]=(vertexes[edges[k].v[0]].origin[0]+vertexes[edges[k].v[1]].origin[0])/2;
								links[linkCount].origin[1]=(vertexes[edges[k].v[0]].origin[1]+vertexes[edges[k].v[1]].origin[1])/2;
								links[linkCount].origin[2]=(vertexes[edges[k].v[0]].origin[2]+vertexes[edges[k].v[1]].origin[2])/2;
								links[linkCount].valid=true;
								xfaces[i].numlinks++;
								linkCount++;
							} else if(xfaces[edgefaces[n].face[1]].type&0x00000002) {
								if(!checkWall(edgefaces[n].face[1],i,n)) {
									return false;
								}
							}
						}
						if(linkCount==65535) {
							printe("Critical Error: Maximum links exceeded\n");
							return false;
						}
					}
				}
			}
		}
	}
	return true;
}

bool readMap(char *mapname) {
	bspHeader_t mapHeader;
	pakHeader_t pakHeader;
	pakDirEntry_t *pakDirEntries;
	char pakFilename[128];
	char bspNames[4][128];
	int bspNum=0;
	char pakNames[16][128];
	int pakNum=0;
	int numDirs;
	int i;
	int length;
	FILE * fh;

	for(i=0;mapname[i];i++) {
		if(mapname[i]>='A' && mapname[i]<='Z') {
			mapname[i]=mapname[i]-('A'-'a');
		}
	}

	strcpy(bspNames[bspNum],quake2Directory);
	strcat(bspNames[bspNum],"baseq2/");
	strcat(bspNames[bspNum++],mapname);
	if(gameDirectory[0]!='\0') {
		strcpy(bspNames[bspNum],quake2Directory);
		strcat(bspNames[bspNum],gameDirectory);
		strcat(bspNames[bspNum++],mapname);
	}
	bspNames[bspNum][0]='\0';

	for(bspNum=0;bspNames[bspNum][0];bspNum++) {
		fh=fopen(bspNames[bspNum],"rb");
		if(fh) {
			fread(&mapHeader,sizeof(mapHeader),1,fh);

			if(mapHeader.ident!=IDBSPHEADER || mapHeader.version!=BSPVERSION) {
				printe("Critical Error: Unrecognized map version\n");
				fclose(fh);
				return false;
			}

			length=mapHeader.planes.size;
			planeCount=length/sizeof(plane_t);
			planes=(plane_t *)malloc(length);
			fseek(fh,mapHeader.planes.offset,0);
			fread(planes,length,1,fh);

			length=mapHeader.vertexes.size;
			vertexCount=length/sizeof(vertex_t);
			vertexes=(vertex_t *)malloc(length);
			fseek(fh,mapHeader.vertexes.offset,0);
			fread(vertexes,length,1,fh);

			length=mapHeader.nodes.size;
			nodeCount=length/sizeof(node_t);
			nodes=(node_t *)malloc(length);
			fseek(fh,mapHeader.nodes.offset,0);
			fread(nodes,length,1,fh);

			length=mapHeader.faces.size;
			faceCount=length/sizeof(face_t);
			faces=(face_t *)malloc(length);
			fseek(fh,mapHeader.faces.offset,0);
			fread(faces,length,1,fh);
 
			length=mapHeader.leaffaces.size;
			leaffaceCount=length/sizeof(unsigned short);
			leaffaces=(unsigned short *)malloc(length);
			fseek(fh,mapHeader.leaffaces.offset,0);
			fread(leaffaces,length,1,fh);

			length=mapHeader.leafs.size;
			leafCount=length/sizeof(leaf_t);
			leafs=(leaf_t *)malloc(length);
			fseek(fh,mapHeader.leafs.offset,0);
			fread(leafs,length,1,fh);

			length=mapHeader.edges.size;
			edgeCount=length/sizeof(edge_t);
			edges=(edge_t *)malloc(length);
			fseek(fh,mapHeader.edges.offset,0);
			fread(edges,length,1,fh);

			length=mapHeader.surfedges.size;
			surfedgeCount=length/sizeof(int);
			surfedges=(int *)malloc(length);
			fseek(fh,mapHeader.surfedges.offset,0);
			fread(surfedges,length,1,fh);

			length=mapHeader.models.size;
			modelCount=length/sizeof(model_t);
			models=(model_t *)malloc(length);
			fseek(fh,mapHeader.models.offset,0);
			fread(models,length,1,fh);

			fclose(fh);
			print("Map: %s\n",bspNames[bspNum]);
			return true;
		}
	}

	strcpy(pakNames[pakNum++],"baseq2/pak0.pak");
	strcpy(pakNames[pakNum++],"baseq2/pak1.pak");
	strcpy(pakNames[pakNum++],"baseq2/pak2.pak");
	strcpy(pakNames[pakNum++],"baseq2/pak3.pak");
	strcpy(pakNames[pakNum++],"baseq2/pak4.pak");
	if(gameDirectory[0]!='\0') {
		strcpy(pakNames[pakNum],gameDirectory);
		strcat(pakNames[pakNum++],"pak0.pak");
		strcpy(pakNames[pakNum],gameDirectory);
		strcat(pakNames[pakNum++],"pak1.pak");
		strcpy(pakNames[pakNum],gameDirectory);
		strcat(pakNames[pakNum++],"pak2.pak");
		strcpy(pakNames[pakNum],gameDirectory);
		strcat(pakNames[pakNum++],"pak3.pak");
		strcpy(pakNames[pakNum],gameDirectory);
		strcat(pakNames[pakNum++],"pak4.pak");
	}
	pakNames[pakNum][0]='\0';

	for(pakNum=0;pakNames[pakNum][0];pakNum++) {
		strcpy(pakFilename,quake2Directory);
		strcat(pakFilename,pakNames[pakNum]);
		fh=fopen(pakFilename,"rb");
		if(fh) {
			length=fread(&pakHeader,sizeof(pakHeader),1,fh);
			if(length==-1) {
				print("Error reading from %s: ",pakFilename);
				return false;
			}
			numDirs=pakHeader.dirsize/0x40;
			pakDirEntries=(pakDirEntry_t *)malloc(pakHeader.dirsize);
			fseek(fh,pakHeader.diroffset,0);
			length=fread(pakDirEntries,pakHeader.dirsize,1,fh);
			if(length==-1) {
				print("Error reading from %s: ",pakFilename);
				free(pakDirEntries);
				return false;
			}
			for(i=0;i<numDirs;i++) {
				if(strcmp(pakDirEntries[i].filename,mapname)==0) {
					fseek(fh,pakDirEntries[i].offset,0);
					fread(&mapHeader,sizeof(mapHeader),1,fh);

					if(mapHeader.ident!=IDBSPHEADER || mapHeader.version!=BSPVERSION) {
						printe("Critical Error: Unrecognized map version\n");
						fclose(fh);
						return false;
					}

					length=mapHeader.planes.size;
					planeCount=length/sizeof(plane_t);
					planes=(plane_t *)malloc(length);
					fseek(fh,pakDirEntries[i].offset+mapHeader.planes.offset,0);
					fread(planes,length,1,fh);

					length=mapHeader.vertexes.size;
					vertexCount=length/sizeof(vertex_t);
					vertexes=(vertex_t *)malloc(length);
					fseek(fh,pakDirEntries[i].offset+mapHeader.vertexes.offset,0);
					fread(vertexes,length,1,fh);

					length=mapHeader.nodes.size;
					nodeCount=length/sizeof(node_t);
					nodes=(node_t *)malloc(length);
					fseek(fh,pakDirEntries[i].offset+mapHeader.nodes.offset,0);
					fread(nodes,length,1,fh);

					length=mapHeader.faces.size;
					faceCount=length/sizeof(face_t);
					faces=(face_t *)malloc(length);
					fseek(fh,pakDirEntries[i].offset+mapHeader.faces.offset,0);
					fread(faces,length,1,fh);
 
					length=mapHeader.leaffaces.size;
					leaffaceCount=length/sizeof(unsigned short);
					leaffaces=(unsigned short *)malloc(length);
					fseek(fh,pakDirEntries[i].offset+mapHeader.leaffaces.offset,0);
					fread(leaffaces,length,1,fh);

					length=mapHeader.leafs.size;
					leafCount=length/sizeof(leaf_t);
					leafs=(leaf_t *)malloc(length);
					fseek(fh,pakDirEntries[i].offset+mapHeader.leafs.offset,0);
					fread(leafs,length,1,fh);

					length=mapHeader.edges.size;
					edgeCount=length/sizeof(edge_t);
					edges=(edge_t *)malloc(length);
					fseek(fh,pakDirEntries[i].offset+mapHeader.edges.offset,0);
					fread(edges,length,1,fh);

					length=mapHeader.surfedges.size;
					surfedgeCount=length/sizeof(int);
					surfedges=(int *)malloc(length);
					fseek(fh,pakDirEntries[i].offset+mapHeader.surfedges.offset,0);
					fread(surfedges,length,1,fh);

					length=mapHeader.models.size;
					modelCount=length/sizeof(model_t);
					models=(model_t *)malloc(length);
					fseek(fh,pakDirEntries[i].offset+mapHeader.models.offset,0);
					fread(models,length,1,fh);

					fclose(fh);
					free(pakDirEntries);
					print("Map: %s %s\n",pakFilename,mapname);
					return true;
				}
			}
			fclose(fh);
			free(pakDirEntries);
		}
	}
	print("Map %s not found\n",mapname);
	return false;
}

void qmUnloadMap(void) {
	__int64 i64_total_time;

	loaded=false;

	if(quake2Directory) free(quake2Directory);
	quake2Directory=NULL;

	if(gameDirectory) free(gameDirectory);
	gameDirectory=NULL;

	if(planes) free(planes);
	planes=NULL;
	
	if(vertexes) free(vertexes);
	vertexes=NULL;

	if(nodes) free(nodes);
	nodes=NULL;

	if(faces) free(faces);
	faces=NULL;

	if(leaffaces) free(leaffaces);
	leaffaces=NULL;

	if(leafs) free(leafs);
	leafs=NULL;

	if(edges) free(edges);
	edges=NULL;

	if(surfedges) free(surfedges);
	surfedges=NULL;

	if(models) free(models);
	models=NULL;

	if(xfaces) free(xfaces);
	xfaces=NULL;

	if(links) free(links);
	links=NULL;

	if(edgefaces) free(edgefaces);
	edgefaces=NULL;

	if(xedges) free(xedges);
	xedges=NULL;

	if(edgefriends) free(edgefriends);
	edgefriends=NULL;

	if(sortededges) free(sortededges);
	sortededges=NULL;

	if(dist) free(dist);
	dist=NULL;

	RDTSC(i64_clock_end);

	i64_total_time=(i64_clock_end-i64_clock_start);

	print("-------- q2map.dll profiling data --------\n");
	print("Your CPU speed is: %.0f MHz\n",clockFrequency()/1000000.0);
	print("Search CPU utilization: %.3f%%\n",100.0*(double)i64_search_time/(double)i64_total_time);
	print("Max search time: %f ms\n",1000.0*(double)i64_max_search_time/clockFrequency());
}

bool qmLoadMap(char *q2dir, char *gamedir, char *mapname, PRINTFUNC p1, PRINTFUNC p2) {
	int len;

	cpuFreq=clockFrequency();

	RDTSC(i64_clock_start);
	i64_search_time=0;
	i64_max_search_time=0;
	setPrintFuncs(p1,p2);

	if(!q2dir) {
		quake2Directory=strdup("c:/quake2/");
	} else {
		len=strlen(q2dir);
		if(len==0) {
			quake2Directory=strdup("c:/quake2/");
		} else if(q2dir[len-1]=='/') {
			quake2Directory=(char *)malloc(len+1);
			strcpy(quake2Directory,q2dir);
		} else {
			quake2Directory=(char *)malloc(len+2);
			strcpy(quake2Directory,q2dir);
			strcat(quake2Directory,"/");
		}
	}
	
	if(!gamedir) {
		gameDirectory=(char *)malloc(1);
		gameDirectory[0]=0;
	} else {
		len=strlen(gamedir);
		if(len==0) {
			gameDirectory=(char *)malloc(1);
			gameDirectory[0]=0;
		} else if(gamedir[len-1]=='/') {
			gameDirectory=(char *)malloc(len+1);
			strcpy(gameDirectory,gamedir);
		} else {
			gameDirectory=(char *)malloc(len+2);
			strcpy(gameDirectory,gamedir);
			strcat(gameDirectory,"/");
		}
	}

	randomize();

	print(VERSION_STRING);

	if(!readMap(mapname)) {
		qmUnloadMap();
		return false;
	}
	if(!linkMap()) {
		qmUnloadMap();
		return false;
	}
	dist=(int *)malloc(faceCount*sizeof(int));

	loaded=true;

	return true;
}

void qmSetBrushLocationFunc(BRUSHLOCATIONFUNC b) {
	;
}

int qmGetAPIVersion(void) {
	return Q2MAP_API_VERSION;
}
